package interview;

public class xiaomi02 {
    boolean FLAG = false;
    public boolean exist(char[][] board, String word) {
        boolean flag = false;
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[i].length; j++){
                flag = dfs(board,word.toCharArray(),0,i,j);
                if (flag){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board,char[] words,int index,int i, int j){

        if ( i < 0 || j < 0 || i > board.length - 1 || j > board[i].length - 1 || board[i][j] == '/'){
            return false;
        }
        if (index == words.length - 1){
            FLAG = words[index] == board[i][j];
            return FLAG;
        }
        char temp = board[i][j];

        boolean flag = false;
        if (board[i][j] == words[index]) {
            index++;
        }

        if (!FLAG) {
            board[i][j] = '/';
            flag = dfs(board, words, index, i - 1, j)
                    || dfs(board, words, index, i, j - 1)
                    || dfs(board, words, index, i + 1, j)
                    || dfs(board, words, index, i, j + 1);
            board[i][j] = temp;
        }else {
            return true;
        }
        return flag;
    }

    public static void main(String[] args) {
        char[][] board = {
                {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','E'}
        };
        String word = "SEE";
        System.out.println(new xiaomi02().exist(board, word));
    }
}
